Image processing apparatus and processes are evaluated in part, for example, by their capability of delivering a complete gray scale at normal viewing distances. This capability is to a certain extent based upon the halftoning techniques employed. Halftoning is a widely used mechanism for converting input intensities represented with multiple bits of information, K (usually K=8) into bilevel or multilevel picture elements (“pels”) with L bits, where L<K. The goal in bilevel halftoning continuous-tone images or multilevel computer generated graphics is to give an illusion of the many shades contained in the original or interpolated multi-bit values per component sample while using only one bit per output sample. Multilevel halftoning allows more than bit per output sample. One traditional technique for halftoning is to create a threshold matrix (usually a different one for each color component) and use it to select a threshold value per sample. The threshold matrix is generally of much smaller dimensions than the image. Halftoning is accomplished by progressing through the input line and the threshold matrix simultaneously, comparing each input intensity with the corresponding threshold value in the threshold matrix. For binary halftoning, if the input intensity is greater than or equal to the threshold value, a fully saturated (e.g. black) corresponding output pel is generated, otherwise the corresponding output pel is white (e.g. Nothing printed). For multilevel halftoning, if the input is within some range of the threshold value, the corresponding output intensity may be an intermediate value. For each line in the image, a given threshold matrix row is cycled through repetitively. The next row is used for the next line. After the last row in the threshold matrix is used, the top row of the threshold matrix is used again.
These threshold matrices are generally referred to as “supercells.” An exemplary supercell and its relationship to basic cells are discussed briefly with reference to FIGS. 1A and 1B. FIG. 1A illustrates the structure of a basic cell 100. In FIG. 1A, the basic cell 100 comprises a 4×4 pel matrix. As described further below, at present, element positions within the basic cell structure 100 are manipulated in a sequential manner (as indicated by the numbers within the elements) to achieve output densities. Incrementing from one output density to the next is accomplished by preserving the current pattern represented by the elements of the basic cell structure 100 and turning on one additional element.
FIG. 1B illustrates an exemplary supercell that is made up of much smaller basic cells such as that depicted in FIG. 1A. The four quadrants of the supercell are labeled to show the order in which the basic cells are filled. In this example, the supercell 150 comprises four basic cells 151–154. The basic cells 151–154 set the halftone's lines per inch thereby determining the level of detail that may be preserved while the size of the supercell 150 determines the number of shades obtainable. According to the current state of the art, a single halftone threshold matrix is used to convert continuous-tone images and graphics into binary or multilevel images. The density of the pels in a region is indicative of the original values in that region, for constant input intensity.
FIG. 1C illustrates using four basic cells to achieve 64 levels by incrementally filling the basic cells in accordance with the ordering of FIG. 1B. If the input image only had 65 levels, i.e., 0 to 64, then FIG. 1C could represent a traditional threshold matrix. Each element contains the comparison, i.e., threshold, value used to determined whether to print the corresponding position in the input image or not. For purposes of this application, the convention of the input value being greater than or equal to the comparison value is employed for the output to be a one (e.g., printed). Of course, this convention is arbitrary and other conventions may be employed. For example, an alternative convention would be to enable (e.g., print) the output pel when the input value is less than or equal to the threshold value.
As illustrated by the prior art basic cell pattern growth example of FIG. 2, N×M+1 output densities may be represented with an N×M halftone matrix for constant input intensities. For example, a 4×4 basic cell halftone matrix allows the generation of 17 densities , i.e., white 201 plus 16 other levels 202–217, to be achieved by turning one and only one element on for each subsequent density. Currently, subsequent densities are generated based upon previous densities by turning one and only one additional element on, thereby requiring patterns for each subsequent density to be a superset of those patterns corresponding to preceding densities For example, once element 220 of the pattern is turned on, it remains on for the rest of the basic patterns. As a result, the number of densities is limited to N×M+1 for constant input intensities. With non-constant input intensities, image detail can cause the output to vary from these basic patterns.
One technique for increasing the number of gray levels (i.e. densities) in halftone reproductions is described by Peter A. Torpey in an article entitled “Using Pixel Overlap to Obtain More Gray Levels in Halftone Reproductions”, Journal of Imaging Technology, Volume 14, Number 2, April 1998. As the title indicates, this method employs pixel (i.e., dot or spot) overlap in any display process where the printed dots are larger than the pixel spacing. In such processes, two pixels, for example, may be printed as neighbors so that they overlap, or far apart, so that they do not overlap. The overlapping pixels will cover less area on the paper and appear lighter than the non-overlapping pixels.
Another approach to increasing the number of densities in a halftone reproduction is described in U.S. Pat. No. 5,867,599 by Michaelis et al., entitled “Screenings of Continuous Tone Images Utilizing Physical Interactions of Adjacent Pixels”. This patent describes a technique for converting continuous tone values to output values while controlling adjacency affects by implementing a lookup table which represents the continuous tone values as addresses in order to provide output patterns to a marking device. The output patterns, when rendered, have substantially the same densities as the corresponding continuous tone values.
Both of the above-referenced techniques have certain disadvantages. For example, the Torpey approach requires an input that is much smaller than the output (e.g. 16:1) and/or employs significant calculating using neighboring pel information (i.e., partial dotting). The Michaelis et al. patent achieves an increased number of densities in halftone reproduction by either indexing the closest (measured) N×M output for a given input (i.e., employs multiple output pels for one input pel ), or uses neighboring output pels in addition to the input intensity to select among tables. In view of the above disadvantages, both approaches are difficult to implement in parallel hardware.
Thus, a need continues to exist in the art for an enhanced technique for providing an increased number of densities for halftone reproduction, and in particular one which employs a point-wise use of multiple threshold matrices with no interaction from neighboring input or output intensities to accomplish the provision of extra densities. The present invention is directed to meeting this need.